🌐 인접 리스트 (Adjacency List)

1️⃣ 개념

인접 리스트(Adjacency List) 는 그래프에서 각 노드와 연결된 노드들을 리스트 형태로 저장하는 방법입니다.

그래프 문제에서 현재 노드와 연결된 노드만 빠르게 탐색하기 위해 가장 많이 사용하는 표현 방식입니다.

🧐 예시

1 - 2
|
3
|
4

간선 정보가

[
  [1,2],
  [1,3],
  [3,4]
]

라면 인접 리스트는

1 → 2, 3
2 → 1
3 → 1, 4
4 → 3

처럼 표현됩니다.

2️⃣ 언제 사용하는가?

✅ 그래프 탐색 문제

노드와 간선으로 이루어진 문제

• 트리
• 그래프
• 네트워크
• 친구 관계
• 도로 연결
• 전력망

✅ DFS / BFS 문제

현재 노드와 연결된 노드만 빠르게 탐색해야 하는 경우

3️⃣ 왜 인접 리스트를 사용할까?

간선 배열 그대로 탐색하면

const wires = [
    [1,2],
    [1,3],
    [3,4]
];

3번 노드와 연결된 노드를 찾기 위해서는

for (const [a, b] of wires) {
    ...
}

처럼 모든 간선을 검사해야 합니다.

하지만 인접 리스트를 사용하면

graph[3]

↓

[1,4]

만 확인하면 됩니다.

즉, 현재 노드와 연결된 노드만 바로 탐색할 수 있습니다.

4️⃣ 인접 리스트 만들기

🧐 간선 정보

const wires = [
    [1,2],
    [1,3],
    [3,4]
];

💻 코드

const graph = Array.from({ length: 5 }, () => []);

for (const [a, b] of wires) {
    graph[a].push(b);
    graph[b].push(a);
}

결과

graph = [
 [],
 [2,3],
 [1],
 [1,4],
 [3]
];

이를 그림으로 표현하면

1 → 2, 3
2 → 1
3 → 1, 4
4 → 3

✍️ 한 줄 정리

인접 리스트는 "각 노드와 연결된 노드들을 저장하는 그래프 표현 방식"이며, 현재 노드에서 이동 가능한 노드만 빠르게 탐색할 수 있어 DFS/BFS 문제에서 가장 많이 사용된다.